Digital data hiding can be used to hide information into multimedia for communication or other use. Most multimedia data hiding techniques distort the original media by inserting hidden data therein, creating marked media. In some cases, the effects on the original cover media caused by the hidden data may not be fully reversible upon extraction of that data. Although the distortion is often small and imperceptible to human visual systems (HVS), the irreversibility is unacceptable for certain sensitive applications, such as legal and medical imaging.
Reversible, or lossless, media data hiding, where the original media is recovered fully after extraction of the hidden data, has wide applications in, among others, law enforcement, medical and military imaging systems, content authentication, covert communications, e-banking, and e-government. As may be appreciated, reversible data hiding is useful in sensitive applications wherein it is desired to prevent permanent loss of signal fidelity. Reversibility means to embed data into digital media, such as images, and restore the original cover media from marked media losslessly. Generally, for data hiding to be reversible, the hidden data is able to be extracted correctly and the marked media is able to be inverted back to the original cover media exactly after the hidden data is extracted.
Two issues commonly arise in attempting to reverse data hiding: data collision and underflow/overflow. Data collision refers to the situation where changed data (including, for example, values of image pixel, transform coefficient, and prediction-error) due to data hiding is confused with the unchanged data during data extraction and original image recovery. Underflow and/or overflow refers to the situation where image grayscale values after data hiding exceed the allowed range from the lower and upper bounds, respectively. For example, the allowed range for pixel values of an 8-bit grayscale image is from 0 to 255. After data embedding, a gray value lower than 0 is referred to as underflow; a gray value higher than 255 is referred to as overflow. For the sake of simplicity, underflow and/or overflow are referred to herein collectively as overflow.
To solve the issues of data collision and overflow/underflow, the bookkeeping data (or histogram modification data) may be required. The manner of handling these issues affects the performance of reversible data hiding in terms of pure payload versus visual quality of marked image (frequently evaluated by peak signal-to-noise ratio (PSNR)).
Early attempts at reversible data hiding, used modulo-256 addition to solve both issues to achieve reversibility. Modulo-256, however, causes salt-and-pepper noise, which is not ideal for most of applications. Lossless compression of bit-planes were then used with limited embedding rate. A regular-singular (RS) method was developed and has achieved relatively high embedding rate. Y. Q. Shi, “Reversible data hiding,” International Workshop on Digital Watermarking, Seoul, Korea, October 2004.
J. Tian, “Reversible data embedding using a difference expansion,” IEEE Transaction on Circuits and Systems for Video Technology, 2003, 13 (8):890-896. This difference expansion method significantly advanced the performance of reversible data hiding in terms of embedding rate versus visual quality of marked image (PSNR). This method uses a location map to address both collision and overflow issues. Following this method, several reversible data hiding schemes using location maps to achieve reversibility with improved performance.
Different methods have been developed using histogram modification. Specifically, one method was developed for addressing overflow using histogram shrinking towards the center. G. Xuan, J Chen, J Zhu, Y. Q. Shi, Z. Ni, and W. Su, “Distortionless data hiding based on integer wavelet transformation,” IEEE Electronics Letters, vol. 38, No. 25, pp. 1646-1648, December 2002. Another method was developed for addressing collision by histogram shifting. This method involves selecting or creating a zero point immediately nearby a peak point in the histogram of a given cover image to embed data reversibly by shifting the whole portion of histogram towards right or left by one unit to avoid collision. Z. Ni, Y Q. Shi, N. Ansari, and W. Su, “Reversible data hiding,” Proceedings of IEEE International Symposium on Circuits and Systems, vol 2, pp. 912-915, Bangkok, Thailand, May 2003.
A further advance combined the above two methods, i.e., histogram shrinking to avoid overflow and histogram shifting to avoid collision. G. Xuan, Y. Q. Shi, C. Yang, Y Zheng, D. Zou, P. Chai, “Lossless data hiding using integer wavelet transform and threshold embedding technique,” IEEE International Conference on Multimedia and Expo (ICME05), Amsterdam, Netherlands, Jul. 6-8, 2005. Various improved schemes have followed this strategy. Instead of always applying histogram shrinking for various images and providing equal amount of histogram shrinkage at both right and left ends, histogram shrinking becomes adaptive. That is, histogram shrinking is not done unless overflow/underflow is detected. As a result, histogram shrinking does not happen for many images as the embedding rate is not very high, and the amount of shrinkage at the two ends, if happening, may not be the same. Instead of choosing a threshold T, then shifting all the portion of histogram h(x) as |x|>T, a new concept of histogram pair is established. Histogram pair is defined as two horizontally immediately neighboring points in histogram such that [h(x)≠0,h(x+1)=0] for x>0 or [h(x−1)=0,h(x)≠0] for x<0. Once a histogram pair is found or created, we can embed data at x. In this way, histogram shifting in data embedding is more flexible. In addition, the embedding points will be within |S|≦|x|≦T (instead of |x|≦T), where S is called as a stop point, and −T≦S≦T. It has been demonstrated that the optimal value of T with respect to the best performance in terms of pure embedding rate versus PSNR of marked image can be searched computationally. G. Xuan, Y Q. Shi, P. Chai, X Cui, Z. Ni, X Tong, Optimum histogram pair based image lossless data embedding, International Workshop on Digital Watermarking (IWDW07), 3-5 Dec. 2007, Guangzhou, China; and G. Xuan, Y Q. Shi, Z. Ni, P. Chai, X Cui, and X Tong, Reversible data hiding for JPEG images based on histogram pairs, International Conference on Image Analysis and Recognition (ICIAR07), Aug. 22-24, 2007, Montreal, Canada. Furthermore, the histogram shrinking can now be executed as an inverse process of histogram pair based data embedding process. That is, after the data embedding histogram become more flat, while after histogram shrinking, the histogram becomes steeper.